package stringoperation;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Hashtable;

// not working yet
public class ParseWords
{
  public static String sentence = "dogsandcats";
  public static HashSet<String> dictionary = new HashSet<String>();

  static {
    dictionary.add("cat");
    dictionary.add("dog");
    dictionary.add("and");
    dictionary.add("sand");
    dictionary.add("dogs");
    dictionary.add("cats");
  }

  public static ArrayList<String> parseSimple(String input, String prefix)
  {
    ArrayList<String> result = new ArrayList<String>();
    if (input.isEmpty() || input == null) {
      result.add(" ");
      return result;
    }

    if ((prefix.isEmpty() || prefix == null) && dictionary.contains(input)) {
      result.add(input);
      return result;
    }

    prefix += input.charAt(0);
    String suffix = input.substring(1);

    if (dictionary.contains(prefix)) {
      result.add(prefix);
      result.addAll(parseSimple(suffix, ""));
    }

    result.addAll(parseSimple(suffix, prefix));

    return result;

  }
  
  //dfs, i think is also backtracking
  static ArrayList<ArrayList<String>> all = new ArrayList<ArrayList<String>>();
  // just return one possible segment
  public ArrayList<ArrayList<String>> segmentString(String s, HashSet<String> dict)
  {
    ArrayList<String> result = new ArrayList<>();
    dfs(result, s, dict, 0);
    return all;
  }

  public void dfs(ArrayList<String> result, String s, HashSet<String> dict,
      int level)
  {
    if (level == s.length()) {
      all.add(new ArrayList<String>(result));
      return;
    }
    for (int i = level + 1 ; i <= s.length() ; i++) {
      String sub = s.substring(level, i);
      if (dict.contains(sub)) {
        result.add(sub);
        dfs(result, s, dict, i);
        result.remove(result.size() - 1);
      }
    }
  }

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub
    ParseWords p = new ParseWords();
    
    System.out.println(p.segmentString(sentence, dictionary).toString());
  }

}
